package com.wk.data.graph;
/**
 * 图 顶点数组 邻接矩阵 邻接表 
 * 边可以有权重 有向图 无向图
 * 状态机是图
 * 图可以使用两种存储结构，分别是邻接矩阵和邻接表。
	邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点：
	1，邻接矩阵是正矩阵，即横纵维数相等。 
	2，矩阵的每一行或一列代表一个顶点，行与列的交点对应这两个顶点的边。 
	3，矩阵的点代表边的属性，1代表有边，0代表无边，所以矩阵的对角线都是0，因为对角线上对应的横纵轴代表相同的顶点，边没有意义。 
	4，如果是无向图，那么矩阵是对称矩阵；如果是有向图则不一定。 
	5，如果是有权图，矩阵点数值可以是权值。 
	6，邻接矩阵表示图的关系非常清晰，但消耗空间较大。
	邻接表是以一组链表来表示顶点间关系，有以下特点:
	1，邻接表示一个有但链表组成的数组 
	2，图中的每一个顶点都有一个链，数组的大小等于图中顶点的个数。 
	3，无向图的链的第一个元素是本顶点，后继分别连接着和这个顶点相连的顶点；有向图的链第一个顶点是本顶点，后继是以本顶点为起点的边的终点。 
	4，如果是有权图，可以在节点元素中设置权值属性 
	5，邻接链表关系表示不如邻接矩阵清晰，数据结构相对复杂，但节省空间。
 * @author wukai
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Graph {
	//顶点数组
	public List<String> vertexList;
	//邻接矩阵 表示边
	public int[][] edges;
	
	public static void main(String[] args) {
		 GraphNode<Integer> node1;
		    GraphNode<Integer> node2;
		    GraphNode<Integer> node3;
		    GraphNode<Integer> node4;
		    GraphNode<Integer> node5;
		    GraphNode<Integer> node6;
		    GraphNode<Integer> node7;
		    GraphNode<Integer> node8;
		    GraphNode<Integer> node9;
		    GraphNode<Integer> node10;
		    node1 = new GraphNode<Integer>(1);
	        node2 = new GraphNode<Integer>(2);
	        node3 = new GraphNode<Integer>(3);
	        node4 = new GraphNode<Integer>(4);
	        node5 = new GraphNode<Integer>(5);
	        node6 = new GraphNode<Integer>(6);
	        node7 = new GraphNode<Integer>(7);
	        node8 = new GraphNode<Integer>(8);
	        node9 = new GraphNode<Integer>(9);
	        node10 = new GraphNode<Integer>(10);

	        node1.neighborList.add(node2);
	        node1.neighborList.add(node3);

	        node2.neighborList.add(node4);
	        node2.neighborList.add(node5);
	        node2.neighborList.add(node6);

	        node3.neighborList.add(node1);
	        node3.neighborList.add(node6);
	        node3.neighborList.add(node7);
	        node3.neighborList.add(node8);

	        node4.neighborList.add(node2);
	        node4.neighborList.add(node5);

	        node5.neighborList.add(node2);
	        node5.neighborList.add(node4);
	        node5.neighborList.add(node6);

	        node6.neighborList.add(node2);
	        node6.neighborList.add(node5);
	        node6.neighborList.add(node3);
	        node6.neighborList.add(node8);
	        node6.neighborList.add(node9);
	        node6.neighborList.add(node10);

	        node7.neighborList.add(node3);

	        node8.neighborList.add(node3);
	        node8.neighborList.add(node6);
	        node8.neighborList.add(node9);

	        node9.neighborList.add(node6);
	        node9.neighborList.add(node8);
	        node9.neighborList.add(node10);

	        node10.neighborList.add(node6);
	        node10.neighborList.add(node9);
	        
//	        GraphSearch<Integer> graphSearch = new GraphSearch<Integer>();
//	        graphSearch.searchDFS(node1);

//	        String expectedSearchPath = "1->2->4->5->6->3->7->8->9->10";
//	        System.out.println(graphSearch.searchPathDFS.toString());
	        
	        GraphSearch<Integer> graphSearch2 = new GraphSearch<Integer>();
	        graphSearch2.searchBFS(node1);

	        String expectedSearchPath2 = "1->2->3->4->5->6->7->8->9->10";
	        System.out.println(graphSearch2.searchPathBFS.toString());
	}
}
/**
 * 无向简单图的节点
 */
class GraphNode<T>{
	T data;
	// 邻接表
	List<GraphNode<T>> neighborList;
	boolean visited;
	public GraphNode(T data) {
		this.data = data;
		neighborList = new ArrayList<GraphNode<T>>();
		visited = false;
	}
	
	public boolean equals(GraphNode<T> node){
        return this.data.equals(node.data);
    }

    /**
     * 还原图中所有节点为未访问
     */
    public void restoreVisited(){
        restoreVisited(this);
    }

    /**
     * 还原node的图所有节点为未访问
     * @param node
     */
    private void restoreVisited(GraphNode<T> node){
        if(node.visited){
            node.visited = false;
        }

        List<GraphNode<T>> neighbors = node.neighborList;
        for(int i = 0; i < neighbors.size(); i++){
            restoreVisited(neighbors.get(i));
        }

    }
}

/**
 * 图的广度优先搜索和深度优先搜索实现
 */
class GraphSearch<T> {

    public StringBuffer searchPathDFS = new StringBuffer();
    public StringBuffer searchPathBFS = new StringBuffer();

    /**
     * 深度优先搜索实现
     *
     * @param root
     */
    public void searchDFS(GraphNode<T> root) {
        if (root == null) {
            return;
        }

        // visited root
        if (searchPathDFS.length() > 0) {
            searchPathDFS.append("->");
        }
        searchPathDFS.append(root.data.toString());
        root.visited = true;

        for (GraphNode<T> node : root.neighborList) {
            if (!node.visited) {
                searchDFS(node);
            }
        }
    }

    /**
     * 广度优先搜索实现,使用队列
     *
     * @param root
     */
    public void searchBFS(GraphNode<T> root) {
        Queue<GraphNode<T>> queue = new LinkedList<GraphNode<T>>();

        // visited root
        if (searchPathBFS.length() > 0) {
            searchPathBFS.append("->");
        }
        searchPathBFS.append(root.data.toString());
        root.visited = true;

        // 加到队列队尾
        queue.add(root);

        while (!queue.isEmpty()) {
            GraphNode<T> r = queue.poll();
            for (GraphNode<T> node : r.neighborList) {
                if (!node.visited) {
                    searchPathBFS.append("->");
                    searchPathBFS.append(node.data.toString());
                    node.visited = true;

                    queue.add(node);
                }
            }
        }
    }
}
